The present invention relates generally to electronic cryptography technology, and in particular to protecting a cryptography device against fault attacks by using linear error correcting codes to determine whether any input, output or intermediate result, involved in performing a cryptographic operations, especially non linear operations such as the SubBytes operation (in case of the AES), has been subjected to a fault attack.
Electronic communication and commerce can be powerful yet dangerous tools. With the wide-spread availability of network technology, such as the Internet, there is an ever increasing use of online tools for communication and commerce. Every year more users find it easier or quicker to conduct important transactions, whether in the form of correspondence or commerce, using computers and computer networks. However, there is always the risk that the security of electronic transactions is compromised through interception by third parties who do not have the right to partake in the transactions. When malicious third parties obtain access to otherwise private transactions and data there is risk of economic loss, privacy loss, and even loss of physical safety. Cryptography is one mechanism employed to avoid intrusion into the privacy of electronic transactions and data.
Cryptography is a technology for hiding a message in the presence of third parties using mathematical techniques in which a message is encrypted in such a way that it can only be decrypted using a secret key that should only be known by the recipient and/or sender of a message.
While cryptographic processes are often complex algorithms and the details thereof are outside the scope of this document. However, at their core cryptographic operations involve repeated combinations of specific substeps that are referred to herein as cryptographic operations. For example, the Advanced Encryption Standard (AES), which serves as an example herein, involves encrypting (or decrypting) a message by performing a sequence of cycles called rounds. Each round operates on a matrix of bytes called a state. Each of the rounds (except for the first round) includes a non-linear operation called SubBytes in which an input byte from the state is substituted with an output byte based on a substitution box (SBox). AES also includes another non-linear step referred to as MixColumns operation. AES is described in Joan Daemen, Vincent Rijmen, The Design of Rijndael: AES—The Advanced Encryption Standard, Springer, 2002.
In a typical software implementation, and for performance reasons, SubBytes is implemented as a lookup table (SBox). In the same way, MixColumns may also benefits from a lookup table representing the polynomial multiplication by x (the so-called XTime operation).
When there is a reason to protect the secrecy of some information, unfortunately, there is a corresponding threat that some unauthorized third party seeks to break that secrecy. One attack mechanism is the so-called Side-channel attacks, which make use of the program timing, power consumption and/or the electronic emanation of a device that performs a cryptographic computation. The behavior of the device (timing, power consumption and electronic emanation) varies and depends directly on the program and on the data manipulated in the cryptographic algorithm. An attacker could take advantage of these variations to infer sensitive data leading to the recovery of a secret key.
Another attack mechanism is the so-called Fault attacks. Fault attacks derive their name from the practice of creating a fault during the computation and exploiting the result produced by that fault to deduce the secret key. Generally, injecting a fault requires a prior step that consists of determining the most likely successful moment for the fault injection. This prior step is usually done by reverse engineering the program through studying the power or the electronic emanation trace. Table lookup operations are particularly vulnerable to fault attacks and can allow the intruder to deduce a secret key, whichever fault effect is caused.
One mechanism used to defend against fault attacks is referred to as Time Redundancy. This includes performing cryptographic operations twice to ensure that no fault has been introduced during the computation by comparing the results of the two computations. Doing operations twice is a costly countermeasure. Time Redundancy is described in T. G. Malkin, et al., A Comparitive Cost/Security Analysis of Fault Attack Countermeasures, Workshop on Fault Detection and Tolerance in Cryptography, August 2005, http://conferenze.dei.polimi.it/FDTC05/Standaert %20-20publisheable.pdf (Accessed May 21, 2005).
Satoh et al. describe the hybrid redundancy, a technique that defends against fault attacks by performing the backward computation of an operation. Akashi Satoh, et al., High-performance Concurrent Error Detection Scheme for AES Hardware, Cryptographic Hardware and Embedded Systems—CHES 2008: 10th International Workshop Lecture Notes in Computer Science Volume 5154, 2008, pp 100-112. Springer.
Another defense mechanism against fault attacks is Information Redundancy. A simple example of information redundancy is parity checking. Information redundancy countermeasures involve the use of error correcting codes. The latter is described in M. G. Karpovsky et al., Robust protection against fault-injection attacks on smart cards implementing the advanced encryption standard, 2004 International Conference on Dependable Systems and Networks. IEEE.
One recent information redundancy mechanisms based on linear codes looks promising for software implementations. Indeed Bringer et al. proposed a masking scheme to thwart both side-channel and fault attacks (Julien Bringer et al., Orthogonal Direct Sum Masking—A Smartcard Friendly Computation Paradigm in a Code, with Builtin Protection against Side-Channel and Fault Attacks, WISTP 2014, https://eprint.iacr.org/2014/665 (accessed on May 26, 2015). However, non-linear operations may be vulnerable to fault attack. In fact, the properties of information redundancy are used before and after the non-linear operation but not during the operation itself, which creates a potential security gap. So far, there is no existing solution based on linear error correcting code that protects globally the whole cryptographic algorithm (both linear and non-linear operations) against fault attacks.
While information redundancy using error-correcting codes provides a useful mechanism for detecting potential injection of a fault into computation values of cryptographic operations, it has hitherto proven difficult to implement such countermeasures efficiently on small devices because to be powerful error detectors the data size of such computation values has to be increased. For example, a C[16,8,5] code doubles the data size from 8-bits to 16-bits. Many cryptographic operations are performed using lookup tables. Lookup tables on 16-bits require approximately 65,000 entries, which is prohibitively large for storing on many constrained cryptographic devices such as smart cards and embedded devices.
From the foregoing it will be apparent that there is still a need for an improved technology to provide a secure mechanism that is computationally efficient, that does not require excessively large storage, and in which a portable security device—e.g., a smart card connected to a host computer—can provide the capability of providing cryptographic services that are protected from fault attacks.